//#ifndef graph_hpp
//#define graph_hpp
//
// Created by 高森森 on 2021/12/30.
//


#include<iostream>
#include<vector>
#include <map>
#include <fstream>
#include <sstream>
#include<set>
#include<queue>

const int limit=500;
using namespace std;

//点的数据
typedef struct Ndata{
    string i;
    Ndata(string _i):i(_i){};
}Ndata;

//节点结构
typedef struct Node{
    int id;
    Ndata *ndata;
    Node(int _id,Ndata* _ndata):
    id(_id),ndata(_ndata){};
    bool operator==(const Node &p1){
        return id==p1.id;
    }
}Node;

/*bool operator < (const Node & p1 ,const Node & p2) //重载比较函数
{
    if(p1.id==p2.id)
        return true;
    return p1.id<p2.id;
}*/

struct NodeCmp{
public:
    bool operator()(const Node *p1, const Node *p2) const {
        if(p1->id!=p2->id)
            return p1->id<p2->id;
        else
            return p1->ndata->i<p2->ndata->i;
    }
};

//边数据
typedef struct EdgeData{
    string weight;
    explicit EdgeData(string _weight):
    weight(std::move(_weight)){};
    bool operator==(const EdgeData &p1){
        return weight==p1.weight;
    }
}EdgeData;

//记录邻接节点
typedef struct Neighbor{
    Node * neighbor;
    EdgeData *edgeData;
    Neighbor():neighbor(nullptr),edgeData(nullptr){};
    Neighbor(Node *_neighbor,EdgeData *_edgeData):
    neighbor(_neighbor),edgeData(_edgeData){};
}Neighbor;

typedef struct NodePair {
    Node *s;
    Node *t;
    NodePair(Node *_s, Node *_t):s(_s),t(_t){} ;

    bool operator<(const NodePair p2) const {
        if (this->s->id != p2.s->id)
            return this->s->id < p2.s->id;
        else {
            return this->t->id < p2.t->id;
        }
    }

    bool operator==(const NodePair p2) const {
        if (this->s->id == p2.s->id && this->s->ndata->i == p2.s->ndata->i && this->t->id == p2.t->id &&
            this->t->ndata->i == p2.t->ndata->i)
            return true;
        return false;
    }
}NodePair;
class Graph {
public:
    map<int,Node*> id2Node;//id到node的映射
    map<Node*,vector<Neighbor*>,NodeCmp> adjacentInList;//每个节点的入度节点
    map<Node*,vector<Neighbor*>,NodeCmp> adjacentOutList;//每个节点的出度节点
    map<NodePair,EdgeData*> nodePair2EdgeData;//保存最后结果集 导出子图
public:
    void buildGraph(char *filename,char * filename2);
    vector<Neighbor*> getInNeighborList(Node* v_ptr);
    vector<Neighbor*> getOutNeighborList(Node* v_ptr);
    int getIdByName( string name);
    string deescapeURL(const string &URL);

};

void Graph::buildGraph(char *filename,char *filename2) {
    string line;
    ifstream infile;
    infile.open(filename);
    if (!infile.is_open()) {
        cout << "Error opening file." << endl;
    }
    while(getline(infile,line)){
        string x = "";
        int y = 0;
        istringstream is(line);
        is >> x >> y;
        Ndata *ndata1 = new Ndata(x);
        Node *node1 = new Node(y, ndata1);
        if (id2Node.find(y) == id2Node.end()) {
            id2Node.insert(make_pair(y,node1));
        }
    }
    /*  ifstream infile2;
      string line2;*/
    infile.close();
    infile.clear();
    infile.open(filename2);
    if (!infile.is_open()) {
        cout << "Error opening file." << endl;
    }

    while (getline(infile, line)) {
        //cout<<line2<<endl;
        int x = 0;
        int y = 0;
        string type = "";
        istringstream is(line);
        is >> x >> y >> type;
        Node *node1 = id2Node[x];
        Node *node2 = id2Node[y];
        EdgeData *edata1 = new EdgeData(type);
        Neighbor* neighbor1=new Neighbor(node1, edata1);
        vector<Neighbor*>neighbors;
        //vector<Neighbor> neighbors;
        //记录入度
        auto it = adjacentInList.find(node2);
        if (it != adjacentInList.end()) {
            auto neighbors = it->second;
            neighbors.push_back(neighbor1);
            adjacentInList[node2] = neighbors;
        } else {
            neighbors.push_back(neighbor1);
            adjacentInList.insert(make_pair(node2, neighbors));
        }

        NodePair nodePair(node1, node2);
        auto it2 = nodePair2EdgeData.find(nodePair);
        if (it2 != nodePair2EdgeData.end()) {
            nodePair2EdgeData[nodePair] = edata1;
        } else {
            nodePair2EdgeData.insert(make_pair(nodePair, edata1));
        }
        //记录出度
        EdgeData *edata2 = new EdgeData(type);
        Neighbor *neighbor2=new Neighbor(node2, edata2);
        vector<Neighbor*>neighbors1;
        auto it3 = adjacentOutList.find(node1);
        if (it3 != adjacentOutList.end()) {
            auto neighbors1 = it3->second;
            neighbors1.push_back(neighbor2);
            adjacentOutList[node1] = neighbors1;
        } else {
            neighbors1.push_back(neighbor2);
            adjacentOutList.insert(make_pair(node1, neighbors1));
        }
    }
    infile.close();
    return;
}


vector<Neighbor*> Graph::getInNeighborList(Node *v_ptr) {
    return adjacentInList[v_ptr];
}
vector<Neighbor*> Graph::getOutNeighborList(Node *v_ptr) {
    return adjacentOutList[v_ptr];
}




short int hexChar2dec(char c) {
    if ( '0'<=c && c<='9' ) {
        return short(c-'0');
    } else if ( 'a'<=c && c<='f' ) {
        return ( short(c-'a') + 10 );
    } else if ( 'A'<=c && c<='F' ) {
        return ( short(c-'A') + 10 );
    } else {
        return -1;
    }
}


string Graph::deescapeURL(const string &URL) {
    string result = "";
    for ( unsigned int i=0; i<URL.size(); i++ ) {
        char c = URL[i];
        if ( c != '%' ) {
            result += c;
        } else {
            char c1 = URL[++i];
            char c0 = URL[++i];
            int num = 0;
            num += hexChar2dec(c1) * 16 + hexChar2dec(c0);
            result += char(num);
        }
    }
    return result;
}

int Graph::getIdByName( string name) {
    cout<<name<<endl;
    name=deescapeURL(name);
    for(auto it=id2Node.begin();it!=id2Node.end();it++){
        if(it->second->ndata->i==name){
            return it->first;
        }
    }
}

class VisitedNode {
public:
    Node* v;
    int depth_bfs;
    vector<VisitedNode*> previous_visited_father;//保存一个节点的父结点
public:
    VisitedNode(Node* _v, int _depth) {
        this->v = _v;
        this->depth_bfs = _depth;
    }
    void addFather(VisitedNode *visitedNode){
        previous_visited_father.push_back(visitedNode);
    }
    void collectTargetPair(char type,set<VisitedNode*>&alreadyCollected,set<NodePair> & targetPair);
};
void VisitedNode::collectTargetPair(char type, set<VisitedNode*> &alreadyCollected, set<NodePair> &targetPair)  {
    //find函数，必须是visitNode 的v,depth_bfs, previous_visited_inBFS 都相同才是同一点
    if(alreadyCollected.find(this)!=alreadyCollected.end()){
        return;
    }
    alreadyCollected.insert(this);
    if(type=='s'){
        for(int i=0;i<previous_visited_father.size();i++)
        {
            Node* s=previous_visited_father[i]->v;
            Node* t=this->v;
            targetPair.insert((NodePair(s,t)));
            previous_visited_father[i]->collectTargetPair(type,alreadyCollected,targetPair);
        }
    }
    else if(type=='t'){
        for(int i=0;i<previous_visited_father.size();i++)
        {
            Node* s=this->v;
            Node* t=previous_visited_father[i]->v;
            targetPair.insert((NodePair(s,t)));
            previous_visited_father[i]->collectTargetPair(type,alreadyCollected,targetPair);
        }
    }
    else{
        cout<<"type must be s or t"<<endl;
    }
}

//step 显示双向路径搜索的深度  direction 1 :出度 -1：入度  id：开始搜索的id，v2visted  记录访问节点
void bfs(int step,Graph&g,int direction,int id,map<Node*,VisitedNode*,NodeCmp>&v2visted){
    Node * v=g.id2Node[id];
    VisitedNode * firstVisited=new VisitedNode(v,0);
    vector<VisitedNode*> currentVisited;
    currentVisited.push_back(firstVisited);
    v2visted[v] = firstVisited;
    for(int s=1;s<=step;s++)
    {
        vector<VisitedNode*>nextVisited;
        for(int i=0;i<currentVisited.size();i++)
        {
            VisitedNode* currentNode=currentVisited[i];
            vector<Neighbor*>neighs;
            if(direction==1)
            {
                neighs=g.getOutNeighborList(currentNode->v);
            }else if(direction==-1){
                neighs=g.getInNeighborList(currentNode->v);
            }else{
                cout<<"direction must be 1 or -1";
            }
            for(int j=0;j<neighs.size();j++)
            {
                Neighbor*n=neighs[j];
                Node * nextNode=n->neighbor;
                VisitedNode *nextVisitedNode;
                auto it=v2visted.find(nextNode);
                if(it==v2visted.end())
                {
                    nextVisitedNode=new VisitedNode(nextNode,s);
                    if(s<step)
                    {
                        //如果重复节点不需要再加入,因为得到它的父亲节点是一样的,已经保存过它的父亲节点了
                        nextVisited.push_back(nextVisitedNode);
                    }
                    v2visted[nextNode]=nextVisitedNode;
                }else{
                    nextVisitedNode=it->second;
                }
                nextVisitedNode->addFather(currentNode);
            }
        }
        if(s<step){
            currentVisited=nextVisited;
        }

    }
}

//前向搜索
void forwardBfs(int stepNum, Graph& g, int source_id, map<Node*, VisitedNode*,NodeCmp>& v2visited) {
    bfs(stepNum, g, 1, source_id,v2visited);
}
//后向搜索
void backwardBfs(int stepNum, Graph& g, int target_id, map<Node*, VisitedNode*,NodeCmp>& v2visited) {
    bfs(stepNum, g, -1, target_id,v2visited);
}

//合并取交
void collectTargerInfo(int s,int t,Graph &g,map<NodePair, EdgeData*> &targetEdgeInfo) {
    map<Node *, VisitedNode *, NodeCmp> s_v2visited;
    //前向搜索
    forwardBfs(2, g, s, s_v2visited);
    map<Node *, VisitedNode *, NodeCmp> t_v2visited;
    //后向搜索
    backwardBfs(2, g, t, t_v2visited);;
    map<Node *, VisitedNode *, NodeCmp>::iterator s_iterator = s_v2visited.begin();
    map<Node *, VisitedNode *, NodeCmp>::iterator t_iterator = t_v2visited.begin();
    set<NodePair> targetEdgeVpair;
    set<VisitedNode *> alreadyCollected;
    int count=0;
    while (count<=limit&&s_iterator != s_v2visited.end() && t_iterator != t_v2visited.end()) {
        Node *v1 = s_iterator->first;
        Node *v2 = t_iterator->first;
        if (v1->id == v2->id && v1->ndata->i == v2->ndata->i) {
            //collectTargetPair 递归收集沿途父结点和关系
            s_iterator->second->collectTargetPair('s', alreadyCollected, targetEdgeVpair);
            t_iterator->second->collectTargetPair('t', alreadyCollected, targetEdgeVpair);
            s_iterator++;
            t_iterator++;
            count++;
        } else if (v1->id < v2->id) {
            s_iterator++;
        } else if (v1->id > v2->id) {
            t_iterator++;
        }
    }
    set<NodePair>::iterator np_itr = targetEdgeVpair.begin();
    cout << targetEdgeVpair.size() << endl;
    while (np_itr != targetEdgeVpair.end()) {
        NodePair vp = *np_itr;
        targetEdgeInfo[vp] = g.nodePair2EdgeData[vp];
        np_itr++;
    }
}



/*int main(){
    Graph g;
    g.buildGraph("C:\\Users\\gcc\\Desktop\\newstars2.txt","C:\\Users\\gcc\\Desktop\\relation_with_id.txt");
    map<NodePair, EdgeData*> targetEdgeInfo;

    int s,t;
//    s=265;
//    t=462;
    string source="黄景瑜";
    string target="张译";
    s=g.getIdByName(source);
    t=g.getIdByName(target);
    collectTargerInfo(s,t,g,targetEdgeInfo);
    for(auto it=targetEdgeInfo.begin();it!=targetEdgeInfo.end();it++)
    {
        cout<<it->first.s->id<<"-->"<<it->first.t->id<<endl;
    }
    string nodes="[";
    set<int>ns;
    for(auto it=targetEdgeInfo.begin();it!=targetEdgeInfo.end();it++)
    {
        ns.insert(it->first.s->id);
        ns.insert(it->first.t->id);
    }
    cout<<ns.size()<<endl;
    for(auto it=ns.begin();it!=ns.end();it++)
    {

        if(it!=--ns.end())
            nodes+="{\"name\":"+std::to_string(g.id2Node[*it]->id)+",\"id\":"+g.id2Node[*it]->ndata->i+"},";
        else{
            nodes+="{\"name\":"+std::to_string(g.id2Node[*it]->id)+",\"id\":"+g.id2Node[*it]->ndata->i+"}";
        }
    }
    nodes+="]";
//    cout<<nodes;
    return 0;
}*/

//#endif




